#include "node.h"
#include <cassert>
#include <map>
#include <set>

enum NodeStatus
{
    UNKNOWN = 0,
    EXISTED = 1,
    TEMP_MARK = 2,
    PERM_MARK = 4
};

void visit(Node *nd, std::map<Node *, NodeStatus> &node_status,
           std::set<Node *> &remaining_nodes, std::vector<Node *> &results)
{
    assert(node_status[nd] & (EXISTED | TEMP_MARK));

    if (node_status[nd] & TEMP_MARK)
    {
        throw std::logic_error("Not a DAG.\n");
    }

    node_status[nd] = TEMP_MARK;

    for (Node *dep : nd->get_dependencies())
    {
        switch (node_status[dep])
        {
        case UNKNOWN:
            node_status[dep] = EXISTED;
            remaining_nodes.emplace(dep);
            visit(dep, node_status, remaining_nodes, results);
            break;
        case EXISTED:
            visit(dep, node_status, remaining_nodes, results);
            break;
        case TEMP_MARK:
            throw std::logic_error("Not a DAG.\n");
        case PERM_MARK:
            break;
        }
    }

    node_status[nd] = PERM_MARK;
    remaining_nodes.erase(nd);
    results.push_back(nd);
}

std::vector<Node *> topo_sort(const std::vector<Node *> &nodes)
{
    std::map<Node *, NodeStatus> node_status;
    std::set<Node *> remaining_nodes;
    std::vector<Node *> results;
    try
    {
        for (auto nd : nodes)
        {
            node_status[nd] = EXISTED;
            remaining_nodes.emplace(nd);
        }

        while (remaining_nodes.size())
        {
            Node *f = *remaining_nodes.begin();
            visit(f, node_status, remaining_nodes, results);
        }

        return results;
    }
    catch (std::logic_error &e)
    {
        std::cerr << e.what();
        return {};
    }
}

int main()
{
    Node a{"a"}, b{"b"}, c{"c"}, d{"d"}, e{"e"}, f{"f"}, g{"g"}, h{"h"};
    // a->d,e, b->d,f, c->d,e, d->e, f->a,c, g->h
    a.dependencies.push_back(&d);
    a.dependencies.push_back(&e);

    b.dependencies.push_back(&d);
    b.dependencies.push_back(&f);

    c.dependencies.push_back(&d);
    c.dependencies.push_back(&e);

    d.dependencies.push_back(&e);

    f.dependencies.push_back(&a);
    f.dependencies.push_back(&c);

    g.dependencies.push_back(&h);

    std::vector<Node *> nodes{&f, &g, &a, &b}; // 只需要提供最高层的几个

    for (auto i : topo_sort(nodes)) // 返回结果是从最底下到最顶上的
        i->print();
}